The present invention relates generally to a cache memory device in an N-way set associative system, and more particularly to a cache memory device capable of detecting a bit error in a reference history without using redundant bits such as parity bits and to a reference history bit error detection method.
In the cache memory device in the N-way set associative system, it has hitherto been known that way information, as shown based on an LRU (Least Recent Used) algorithm, exhibiting the earliest time of being referred to (or updated) for the last time within the same set, is written back to a main storage device (main memory), and this scheme is advantageous in terms of performance.
An operation of the conventional cache memory device will be explained with reference to the drawings. FIG. 8 is an explanatory flowchart showing the operation of the conventional cache memory device.
When an access request to a specified address in an address space of the main memory (S200), to begin with, this address is separated into a match address and a line address. A tag RAM of each way is searched according to the line address, and an entry address read from the tag RAM is compared with the match address (S201). If the entry address is coincident with the match address, this implies that the way concerned is hit (S202: Yes). In this case, the hit way is sent back, and there is effected an access to a copy of the main memory that is retained on a data RAM of the way concerned (S203).
Whereas if the match address hits none of the entry addresses of the ways (S202: No), information of a certain way is written back (or invalidated) and thrown away from the entry of the tag RAM, and the copy of the main memory having an address corresponding to the access request is read into a cache. A reference history is read for selecting this throw-out way (replace target way) (S204) Next, it is judged whether a 1-bit error in the reference history is detected (S205). This error detection is executed based on redundant bits attached to the readout reference history (which may be called, e.g., a parity check). Then, if the parity check occurs (S205: Yes), it is considered that this reference history contains an error, and an error report is made (S206). Then, a way having the lowest number among the valid ways is sent back (S207). Further, in the case of making a win/loss decision based on the reference history, if there occurs a contradictory in a reference time relation, the same process as when the parity error occurs has hitherto been executed in order to prevent zero-select or double-select of the way.
The write-back to the main memory involves retaining, in a tag memory (or a memory area that can be referred to by the set equal thereto), the reference history (which may also be called LRU bits) capable of making a comparison between earliness and lateness of the reference time within the same set. Further, according to a device requested to have a reliability, the redundant bits such as the parity bits, ECC (Error Correcting Code) and so on are added to the reference history.
If the system increases in scale with an extended address space, a must-be-cached address space likewise increases. If a block size of the cache is the same, each time the cacheable address space is doubled, it follows that a data size of the entry address in the tag memory increases by 1 bit. At this time, there might be a case where the redundant bits for detecting the error in the reference history can not be sufficiently ensured due to a restraint of the data size in the tag memory and so on.
It is an object of the present invention to detect the bit error in the reference history without adding the redundant bits to the reference history in the cache memory device in the N-way set associative system.